#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <malloc.h>
#include "automata2.h"
#include "util.h"
#include "testInputs.h"
#include "longInt.h"
#define NO_DEBUG

t_int_vector seen;

int 
main(int argc, char *argv[])
{
    t_table t;
    FILE * fIn, * fOut;
    char fileName[50];
    int i,aux;
    
    if(argc!=2)
        error(1,"Use: blabla file\n(file must have \"in\" extension)");

    strcpy(fileName,argv[1]);
    if((fIn = fopen(strcat(argv[1],".in"),"r"))==NULL)
        error(1,"Could not open file. Check file name is correct.");
    
    t = parseFile(fIn);
    
#ifdef DEBUG

    //Display transition table
    printTable(&t);     
    //Print states
    printStates(&t);

    printf("\n-----------------------------------------------------\n");
    printf("Now removing lambda transitions:\n\n");
 //   removeLambdaTrans(&t);
    
    //Display transition table
    printTable(&t);
    //Print states
    printStates(&t);
  	//Print alhpabet symbols
	printAlphabet(&t);
    //Print input chains
    printf("\nPrinting input chains...\n");
    for(i=0;i<t.input.dim;i++)
        printf("%s\n",t.input.chains[i]);
    //Print final states    
    
    printf("\nPrinting final states...\n");        
    for(i=0;i<t.finalStates.dim;i++)
        printf("%d: %d\n",i,t.finalStates.vec[i]);
#endif


    removeLambdaTrans(&t);
    nfaToDfa(&t);
    MinimizeDFA(&t);
    testInput(&t);
    
//    printf("\nAl minimizar:\n\n");
//    printTable(&t);


    if((fOut = fopen(strcat(fileName,".out"),"w"))==NULL)
        error(1,"Could not open file for writing");
    writeFile(fOut,&t);
    fclose(fOut);
    system("PAUSE");	
    
    //Releasing memory
    free(t.alphabet);
    for(i=0;i<t.input.dim;i++)
        free(t.input.chains[i]);
    free(t.input.chains);
    free(t.finalStates.vec);
    free(t.states.vec);
    for(i=0;i<t.transitions.fils;i++)
        free(t.transitions.data[i]);
    free(t.transitions.data);

    system("PAUSE");	
    return 0;
}

t_matrix
buildMatrix(int fil, int col)
{
    int i,j;
    t_matrix out;
    
    out.fils=fil;
    out.dimFils=fil+30;
    out.cols=col;
    if((out.data = malloc(sizeof(int *)*out.dimFils))== NULL)
        error(1,"Could not allocate memory. Shame on you.");
    
    for(i=0;i<out.dimFils;i++)
        out.data[i]=malloc(sizeof(int)*col);

    //Fill matrix with -1 which means the trap/error state transition
    for(i=0;i<out.dimFils;i++)
        for(j=0;j<col;j++)
            out.data[i][j] = -1;
            
    return out;
}


void
writeFile(FILE * f, t_table * t)
{
    int i,j,alphabetDim;
    
    alphabetDim = strlen(t->alphabet);
    
    //Print Alphabet
    fprintf(f,"%s\n",t->alphabet);
    //Print number of states
    fprintf(f,"%d\n",t->states.dim);
    //Print initial state
    fprintf(f,"%d\n",t->iniState);
    //Print final states
    for(i=0;i<t->finalStates.dim-1;i++)
        fprintf(f,"%d ",getStateIndex(t,t->finalStates.vec[i]));
    fprintf(f,"%d\n",getStateIndex(t,t->finalStates.vec[i]));
    //Print transitions
    for(i=0;i<t->transitions.fils;i++)
        for(j=0;j<alphabetDim;j++)
            fprintf(f,"%d %d %c\n",i,t->transitions.data[i][j],t->alphabet[j]);
    fprintf(f,"\n");
    for(i=0;i<t->input.dim-1;i++)
        fprintf(f,"%s\n",t->input.chains[i]);
    fprintf(f,"%s",t->input.chains[i]);
}

/* Parse input - loads Nondeterministic Finite Automata into memory */
t_table 
parseFile(FILE * f)
{
    t_table t;
    t_matrix m;
    t_int_vector v;
    t_input in;
    char c, * alpha, buf[BUF_SIZE], buf2[BUF_SIZE], * toks, symbol;
    int cantSym, from_state, to_state, symbol_index, i;
    void * aux;
        
    //Reading alphabet - 1st line
    if((alpha = malloc(BUF_SIZE))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    cantSym = getline(alpha, BUF_SIZE, f);
    if((aux = realloc(alpha, cantSym + 1))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    else
        t.alphabet = aux;

    //2nd line - states
    getline(buf,BUF_SIZE,f);
    t.originalDim = atoi(buf);
    t.states.dim = atoi(buf);
    t.states.maxDim = atoi(buf);
    if(t.states.dim > 31)
        error(1,"Not able to process NFA with more than 31 states\n");
    if((t.states.vec = malloc(t.states.maxDim*sizeof(int)))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    for(i=0;i<t.states.dim;i++)
        t.states.vec[i]=i;
    
    //3rd line
    getline(buf,BUF_SIZE,f);
    t.iniState = atoi(buf);
    
    //4th line
    getline(buf,BUF_SIZE,f);
    strcpy(buf2,buf);
    toks = strtok(buf," ");
    i=0;
    while(toks != NULL)
    {
        i++;
        toks = strtok(NULL," ");
    }
    t.finalStates.dim=i;
    t.originalFinalDim=i;
    if((t.finalStates.vec = malloc(i * sizeof(int)))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    i=0;
    toks = strtok(buf2," ");
    while(toks != NULL)
    {
        t.finalStates.vec[i++]=atoi(toks);
        toks = strtok(NULL," ");
    }
    
    //Build transitions matrix
    m = buildMatrix(t.states.dim,cantSym+1); //add extra symbol: lambda
    t.transitions = m;
    //Rest of the file, until input lines
    while(getline(buf,BUF_SIZE,f))
    {
	    if(*buf == '\r')
		    break;
        from_state = atoi(strtok(buf," "));
        to_state = atoi(strtok(NULL," "));
        if((toks = strtok(NULL," "))==NULL) //Lambda transition
            symbol = '^';
        else
            symbol = *toks;
        if(from_state > t.states.dim-1 || to_state > t.states.dim-1)
            error(1,"Malformed input file - using more states than declared");
        symbol_index = getSymIndex(t.alphabet,symbol);
        addTransition(&t,from_state,symbol_index,to_state);
    }
    
    //Input chains for processing
    if((in.chains = malloc(10 * sizeof(char *)))==NULL)
        error(1,"Could not allocate memory. Shame on you.");
    in.dim = 0;
    while(1)
    {
        if(getline(buf,BUF_SIZE,f)==0 && *buf != '\0')
            break;
        in.chains[in.dim]=malloc(strlen(buf)+1);
        strcpy(in.chains[in.dim++],buf);
        
        //Need to allocate more space
        if(in.dim%10 == 0)
        {
            if((aux = realloc(in.chains, ((in.dim/10)+1)*10*sizeof(char *)))==NULL)
                error(1,"Could not allocate memory. Shame on you.");
            else
                in.chains = aux;
        }
    }
    
    t.input = in;
   
    fclose(f);
    return t;
}

/* Retrieves symbol index from alphabet*/
int
getSymIndex(char * alphabet, char symbol)
{
    int i,len;

    len=strlen(alphabet);

    //If it's a lambda transition, then return last matix column index    
    if(symbol == '^')
        return len;
    
    for(i=0;i<len;i++)
        if(alphabet[i] == symbol)
            break;
    
    return i;
}

/* Adds a transition to the transition's matrix*/
void
addTransition(t_table * t, int from_state, int symbol_index, int to_state)
{
    int state, prevSt, aux;

    prevSt = t->transitions.data[from_state][symbol_index];
    if(prevSt == -1)
    {
        t->transitions.data[from_state][symbol_index] = to_state;
        return ;
    }


    if (isSelfContained(t->originalDim, prevSt, to_state))
        state=prevSt;
    else
    {
        aux = (prevSt < t->originalDim)? (1<<prevSt) : 
            t->states.vec[prevSt] - t->originalDim;
        state = aux+(1<<to_state)+t->originalDim;
    }
    
    t->transitions.data[from_state][symbol_index] = 
        getStateIndex(t, state);            
}

int
isSelfContained(int origDim, int oldSt, int newSt)
{
    return 0;    
}

int
getStateIndex(t_table * t, int state)
{
    int i, j, found, finSt=0;
    void * aux;
    
    if(state == -1)
        return -1;
    
    for(i=0,found=0;i<t->states.dim;i++)
        if(t->states.vec[i]==state)
        {
            found=1;
            break;
        }

    //Add a new state
    if(!found)
    {
        if(t->states.dim == t->states.maxDim)
        {
            if((aux=realloc(t->states.vec,sizeof(int)* (t->states.maxDim *= 2)))==NULL)
                error(1,"Could not allocate memory. Shame on you.");
            else
            {
                t->states.vec = aux;
            }
        }
        t->states.vec[t->states.dim++] = state;        
    
        //Check if new state is an acceptance one, then add it
        for(j=0;j<t->originalFinalDim;j++)
            if(t->finalStates.vec[j] < t->originalDim)
                finSt|= 1<< t->finalStates.vec[j];
            else
                finSt|= state - t->originalDim;
        if(finSt & (state - t->originalDim))
        {
            if((aux=realloc(t->finalStates.vec,
                (t->finalStates.dim+1) * sizeof(int)))==NULL)
                error(1,"Could not allocate memory. Shame on you.");
            else
                t->finalStates.vec=aux;
            t->finalStates.vec[t->finalStates.dim++]=state;
        }          
    } 
        
    
    
    return i;
}

/* Reads a line, returns its length*/
int
getline(char * line, int max, FILE * f)
{
    int cant;
    
    if(fgets(line, max, f)==NULL)
        return 0;
    else{
        cant = strlen(line)-1;
        if(line[cant]=='\n')
        {
            line[cant]='\0';
            return cant;
        }
        else
            return cant+1;
    }
}

void
removeLambdaTrans(t_table * t)
{
    int i, alphabetDim, cl, j, k, newState, aux, aux2;
    
    alphabetDim = strlen(t->alphabet);
  
/*    if((seen.vec=malloc(100*sizeof(int)))==NULL)
        error(1,"se cago el malloc cableado\n");
  */
    for(i=0;i<t->originalDim;i++)
    {  
        cl = t->transitions.data[i][alphabetDim];
        setLambdaClosure(i,t,&cl);
	if(seen.dim>0)
		free(seen.vec);
        seen.dim=0;
//        printf("clausura lambda del estado %d: %d (%d)\n",i,cl,cl==-1?-1:t->states.vec[cl]);
//        system("pause");
        
        for(j=0;j<alphabetDim;j++)
        {
            if(cl >= t->originalDim)
            {
                for(k=0;(1<<k)+t->originalDim<t->states.vec[cl];k++)
                    if((1<<k)&(t->states.vec[cl]-t->originalDim))
                    {
                        aux = (t->transitions.data[i][j] == -1)? -1 : 
                            t->states.vec[t->transitions.data[i][j]];
                        aux2 = (t->transitions.data[k][j] == -1)? -1 :
                            t->states.vec[t->transitions.data[k][j]];
                        newState = composeStates(t->originalDim,aux,aux2);
                        t->transitions.data[i][j] = getStateIndex(t,newState);
                    }
            }
            else
            {
                aux = (t->transitions.data[i][j] == -1)? -1 : 
                    t->states.vec[t->transitions.data[i][j]];
                aux2 = (cl == -1)? -1 :
                    (t->transitions.data[cl][j] == -1)? -1 : 
                        t->states.vec[t->transitions.data[cl][j]];
                newState = composeStates(t->originalDim,aux,aux2);
                t->transitions.data[i][j] = getStateIndex(t,newState);
            }
        }
    }
    for(i=0;i<t->originalDim;i++)
        t->transitions.data[i][alphabetDim]=-1;
}


void
setLambdaClosure(int state, t_table * t, int * cl)
{
    int i,lambdaTo, alphabetDim, newState, aux, aux2, aux3;
    double result;

    alphabetDim = strlen(t->alphabet);
    lambdaTo = t->transitions.data[state][alphabetDim];
    if(lambdaTo == -1 || lambdaTo == state || alreadySeen(lambdaTo))
        return ;
    
    markAsSeen(state);
    
    if(lambdaTo >= t->originalDim)
    {
        for(i=0;(1<<i)+t->originalDim<t->states.vec[lambdaTo];i++)
            if((1<<i)&(t->states.vec[lambdaTo]-t->originalDim))
            {
                if(alreadySeen(i))
                    continue;
                t->transitions.data[state][alphabetDim] = i;
                setLambdaClosure(state,t,cl);
            }
        //Restore info
        t->transitions.data[state][alphabetDim] = lambdaTo;
        return ;
    }
        
    setLambdaClosure(lambdaTo,t,cl);
    
    aux = t->states.vec[*cl];
    aux2 = t->states.vec[lambdaTo];
    newState = composeStates(t->originalDim,aux,aux2);
    *cl = getStateIndex(t,newState);    
}

int
alreadySeen(int state)
{
    int i;
    
    for(i=0;i<seen.dim;i++)
        if(seen.vec[i] == state)
            break;
            
    return seen.dim != i;
}

void
markAsSeen(int state)
{
    void * aux;
    
    if(seen.dim==0)
    {
            if((seen.vec = malloc(((seen.dim/10)+1)*10*sizeof(int)))==NULL)
                error(1,"Could not allocate memory. Shame on you.");
    }	    
    else if(seen.dim % 10 == 0)
    {
            if((aux = realloc(seen.vec, ((seen.dim/10)+1)*10*sizeof(int)))==NULL)
                error(1,"Could not allocate memory. Shame on you.");
            else
                seen.vec = aux;
    }
    seen.vec[seen.dim++]=state;
}


int
composeStates(int originalDim, int receiver, int giver)
{
    if(receiver == -1 || receiver == giver)
        return giver;
    if(giver == -1)
        return receiver;
    receiver = (receiver<originalDim)? (1<<receiver) : (receiver-originalDim);
    giver = (giver<originalDim)? (1<<giver) : (giver-originalDim);
        
    
    return (receiver | giver) + originalDim;
}




